# coding: utf-8
# 单向链表实现
# 单向链表的3个核心方法：插入、删除、查找（每次都要从表头开始）
# 不带表头的单向链表在实现插入和删除时必须区分【头结点】和【其他节点】的处理，带表头就不用区分。
# 关键词：head（表头），p（prev），q（next），pq遍历链表。

class Node:
    def __init__(self,x):
        self.val = x
        self.next = None

    def __repr__(self):
        return "Node[val={val}, next={next}]".format(val=self.val,next=id(self.next))
    
class SingleLinkedList:
    def __init__(self):
        # 表头是一个空节点，这样可以不用区分头节点和其他节点
        self.head=Node(None)
        # self.tail=None 单向链表tail没有意义，双向链表才有意义
        self.length=0

    def __repr__(self):
        str="Head[val={val}, length={length}]".format(val=self.head.val,length=self.length)
        p=self.head  #p表示prev
        q=self.head.next  #q表示next（因为q在p的后面）
        while q:
            str+="-->Node[{val}]".format(val=q.val)
            q = q.next
        return str

    def insert(self,dataNode,index):
        """
        插入数据节点dataNode
        index从0开始（与数组一致）
        """
        if index<0 or index>self.length:
            raise Exception("出界了 {idx}".format(idx=index))

        i=0
        #pq双指针遍历链表，p指向表头，q指向第一个元素
        p = self.head
        q = self.head.next
        while q and i<index:
            p,q = q,q.next
            i+=1
        # 只需处理前面元素的指向
        p.next,dataNode.next = dataNode,q
        self.length+=1

    def delete(self,index):
        """
        删除节点
        index从0开始
        """
        if index<0 or index>=self.length:
            raise Exception("出界了")

        i=0
        p = self.head
        q = self.head.next
        while q and i<index:
            p,q = q,q.next
            i+=1
        #绕过q
        p.next = q.next
        self.length-=1
        return q

    #链表核心操作之一：从头开始查找
    def search(self,item):
        #典型的链表遍历操作
        p=self.head
        q=self.head.next
        while q:
            if q.val==item:
                return q
            p,q=q,q.next
        return None
    
    #链表核心操作之一：获取前一个元素（从头查找）
    #对链表进行二分查找、排序，离不开这个prev操作
    def prev(self,node):
        p=self.head
        q=self.head.next
        while q:
            if (q==node):
                #有可能返回表头
                return p
            p,q=q,q.next
        return None

    #最没用的方法（不如prev方法，at对于链表太多异常的情况了，容易把问题复杂化）
    def at(self,index):
        if index<0 or index>=self.length:
            raise Exception("出界了")

        p=self.head
        q=self.head.next
        i=0
        while q and i<index:
            p,q=q,q.next
            i+=1
        return q

    #交换：p->q变成q->p
    def swap(self,p,q):
        pp=self.prev(p)
        if pp==None:
            raise Exception("p没有前置元素")
        #python的好处是交换不需要中间元素temp（原理：python并不交换值，而是交换地址）
        pp.next,q.next,p.next=q,p,q.next

    def smaller(self,node):
        p=self.head
        q=self.head.next
        while q and q.val<=node.val:
            p,q=q,p.next
        return p

    #相邻swap适合数组，因为数组远距离移动元素很慢；远距离swap适合链表，链表很快；由此导致链表和数组的插入排序差别比较大。
    #swap: 数组--相邻swap，链表--远距离swap。
    #https://leetcode-cn.com/problems/insertion-sort-list/
    def insertionSort(self):
        if self.length<=1:
            return
        p=self.head
        q=self.head.next
        while q:
            if p.val<=q.val:
                p,q=q,q.next
                continue
            #找到一个逆序p.val>q.val，尝试找出q的正确位置
            pp=self.smaller(q)
            #修改next指针
            pp.next,q.next,p.next=q,pp.next,q.next
            #下一次循环
            q=p.next

#TODO
class LinkedLRUCache(object):
    pass

print(Node(10))

sll = SingleLinkedList()
sll.insert(Node(1),0)
sll.insert(Node(11),0)
sll.insert(Node(2),0)
sll.insert(Node(22),0)
sll.insert(Node(-1),0)
sll.insert(Node(-2),sll.length)
sll.delete(2)
print(sll)

print(sll.search(-2))

s=sll.search(1)
print(sll.prev(s))

idx=0
print("at {idx}".format(idx=idx), sll.at(idx))
idx=4
print("at {idx}".format(idx=idx), sll.at(idx))
print("smaller:",sll.smaller(sll.at(3)))

idx=3
aa=sll.at(idx)
sll.swap(aa,aa.next)
print(sll)

print("insertion sort:")
sll.insertionSort()
print("sort result:",sll)
